package leetcode.editor.cn;

//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 示例 3： 
//
// 
//输入：s = "a"
//输出："a"
// 
//
// 示例 4： 
//
// 
//输入：s = "ac"
//输出："a"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母（大写和/或小写）组成 
// 
// Related Topics 字符串 动态规划 👍 4530 👎 0

//Java：最长回文子串
public class LongestPalindromicSubstring_5{
    public static void main(String[] args) {
        Solution solution = new LongestPalindromicSubstring_5().new Solution();
        // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String longestPalindrome(String s) {
        int length = s.length();
        if(length<=1) return s;
        char[] chars = s.toCharArray();
        int maxLen =0, maxIndex = 0;
        for (int i = 0; i < length; i++) {
            int length1 = middleDiffusion(chars, i, i);
            int length2 = middleDiffusion(chars, i,i+1);
            int max = Math.max(length1, length2);
            if(max>maxLen){
                maxLen = max;
                maxIndex = i-(max-1)/2;
            }
        }
        return s.substring(maxIndex, maxIndex+maxLen);
    }

        /**
         * 中心扩散法
         */
    public int middleDiffusion(char[] chars, int left,int right){
        while (left>=0 && right<chars.length){
            if(chars[left] == chars[right]){
                left--;
                right++;
            }else break;
        }
        return right-left-1; // (right-left+1)-2
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    /**
     * 动态规划
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
    int length = s.length();
    if(length<=1) return s;
    boolean[][] dp = new boolean[length][length]; // dp[i][j] 表示substring(i,j)是否为回文串
    for (int i = 0; i < length; i++) {
        dp[i][i] = true;
    }
    int maxLen=1, maxIndex=0; // 至少存在长度为1的子串
    char[] chars = s.toCharArray();
    for (int l = 2; l <= length; l++) { // 子串长度
        for (int i = 0; i < length; i++) { // 起始位置
            int j=i+l-1;   // 结尾位置
            if(j>=length) break;
            if(chars[i]!=chars[j]){
                dp[i][j]=false;
            }else{
                if(l<4) // 子串长度为2or3
                    dp[i][j] = true;
                else{
                    dp[i][j] = dp[i+1][j-1];
                }
            }
            if(dp[i][j] && l>maxLen){
                maxLen=l;
                maxIndex =i;
            }
        }
    }
    return s.substring(maxIndex, maxIndex+maxLen);
}
}
